use std::collections::HashMap;
use super::solution::Solution;

impl Solution {
    pub fn maximize_win(prize_positions: Vec<i32>, k: i32) -> usize {

        let mut cache= [0].repeat(prize_positions.len());
        let mut m=0;
        let mut  ans =0;
        for ind in 0..prize_positions.len() {
            if prize_positions[ind]< k {
                m+=1;
                cache[ind] = m;
                continue
            }
            let ii=Self::binary_search(&prize_positions[0..ind+1],prize_positions[ind]-k);
            let mut one_score=ind+1;
            let mut two_score=0;
            if let Some(iii)=ii{
                    one_score=ind-iii;
                    two_score=cache[iii] ;

            }

            if ans<one_score+two_score {
                ans = one_score+two_score;
            }
            if one_score > m {
                cache[ind] = one_score;
            }

        };
        ans
    }
    fn binary_search(prize: &[i32], target: i32) -> Option<usize> {
        let (mut left,mut right) = (0, prize.len()-1);
        while left < right {
            let mid =right-(right-left)/2;
            if prize[mid]>=target {
                if mid ==0{
                    return None
                }
                right = mid-1;
            }else{
               left = mid;
            }
        }

            if prize[left]>=target {
                return None

            }
            Some(left)

    }
}

#[cfg(test)]
mod tests {
    use crate::solution::Solution;

    #[test]
    fn test_maximize_win() {
        Solution::maximize_win(vec![1,2,3,4], 0);
    }
}